package special;

import java.util.HashMap;
import java.util.Map;

class MajorityChecker {
    int[] arr;
    public MajorityChecker(int[] arr) {
      this.arr = arr;
    }
    
    public int query(int left, int right, int threshold) {
       int[] map = new int[20001];
        for (int i = left; i <= right; i++) {
            if (++map[arr[i]] >= threshold){
                return arr[i];
            }
        }
        return -1;
    }
}